package com.jackie.algo.geek.time.chapter11_sort;

/**
 * @Author: Jackie
 * @date 2019/1/13
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = new int[]{100,82,74,62,54,147};
        insertSort(arr);
    }

    /**
     * 借用https://www.cnblogs.com/bjh1117/p/8335628.html文中的举例，我们可以看到一个完整的插入排序的过程
     * 通过这个过程，我们可以更好的理解插入排序的思想
     * 待比较数据：7, 6, 9, 8, 5,1
     *
     * 　　第一轮：指针指向第二个元素6，假设6左面的元素为有序的，将6抽离出来，形成7,_,9,8,5,1，从7开始，6和7比较，发现7>6。将7右移，形成_,7,9,8,5,1，6插入到7前面的空位，结果：6,7,9,8,5,1
     *
     * 　　第二轮：指针指向第三个元素9，此时其左面的元素6,7为有序的，将9抽离出来，形成6,7,_,8,5,1，从7开始，依次与9比较，发现9左侧的元素都比9小，于是无需移动，把9放到空位中，结果仍为：6,7,9,8,5,1
     *
     * 　　第三轮：指针指向第四个元素8，此时其左面的元素6,7,9为有序的，将8抽离出来，形成6,7,9,_,5,1，从9开始，依次与8比较，发现8<9，将9向后移，形成6,7,_,9,5,1，8插入到空位中，结果为：6,7,8,9,5,1
     *
     * 　　第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,_,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成_,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1。
     *
     * 　　第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9。
     *
     * 所以插入排序是保证一个元素的左边所有元素都是有序的，然后逐渐右移，直到遍历完所有的元素来保证整个数据是有序的
     * 下面i从1开始，是表示以a[1]作为哨兵，第一次比较是a[0]和其比较，这里的j的其实位置都是小于i一个位移，即j=i-1
     * 然后依次从右向左挨个比较，如果发现哨兵值小于左侧有序集合，则一直位移，以此保证始终留有一个位置用于插入待排序的值
     * 一旦发现哨兵值如果大于等于（保证稳定性，即不会跑到等于某个值的左侧）左侧集合中的某个值，
     * 则跳出内层循环，仔细想想左侧集合是有序的就明白了
     * 至于最后为什么是a[j+1]=value，直觉上更应该是a[j]=value，但是记得，在跳出内层循环的时候进行了一次j--操作，
     * 所以需要把这个操作补偿进来，变成了j+1
     */
    public static void insertSort(int arr[]) {
        int length = arr.length;
        if (length <= 1) {
            return;
        }

        for (int i = 1; i < length; i++) {
            int value = arr[i];
            int j = i - 1;

            for (; j >= 0; j--) {
                if (arr[j] > value) {
                    arr[j+1] = arr[j];  // 位移
                } else {
                    break;
                }
            }

            arr[j+1] = value;
        }

        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
